package com.zwh.algorithm.leetcode.medium;

import java.util.*;
import java.util.stream.Collectors;

public class LeetCode90 {
    /**
     * 2025-08-10  子集II
     * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。
     * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
     * 示例 1：
     *
     * 输入：nums = [1,2,2]
     * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
     * 示例 2：
     *
     * 输入：nums = [0]
     * 输出：[[],[0]]
     *
     *
     * 提示：
     *
     * 1 <= nums.length <= 10
     * -10 <= nums[i] <= 10
     */
    public static void main(String[] args) {
        System.out.println(subsetsWithDup(new int[]{1,1,1,2,2,2}));
    }
    //回溯算法
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> ans = new HashSet<>();
        List<Integer> cur = new ArrayList<>();
//        dfs1(nums,0,cur,ans);
        dfs2(nums,0,cur,ans);
        return new ArrayList<>(ans);

    }

    public static void dfs1(int[] nums,int u,List<Integer> cur,Set<List<Integer>> ans){
        //所有位置决策完成
        if (nums.length == u){
            ans.add(new ArrayList<>(cur));
            return;
        }
        //选择当前位置的元素，往下决策
        cur.add(nums[u]);
        dfs1(nums,u + 1,cur,ans);
        //不选当前位置的元素（回溯），往下决策
        cur.remove(cur.size() - 1);
        dfs1(nums,u + 1,cur,ans);
    }

    public static void dfs2(int[] nums,int u,List<Integer> cur,Set<List<Integer>> ans){
        //所有位置决策完成
        int n = nums.length;
        if (n == u){
            ans.add(new ArrayList<>(cur));
            return;
        }
        //记录当前位置是什么数值（令数值为t），并找出数值为t的连续一段
        int t = nums[u];
        int last = u;
        while (last< n && nums[last] == nums[u]){
            last++;
        }
        //不选当前位置的元素，直接跳到last往下走
        dfs2(nums,last,cur,ans);
        //决策选择不同个数的t的情况
        for (int i = u;i < last; i++){
            cur.add(nums[i]);
            dfs2(nums,last,cur,ans);
        }
        //回溯对数值t的选择
        for (int i = u; i < last; i++){
            cur.remove(cur.size() - 1);
        }
    }

}
